As a technology for verifying the integrity of electronic documents (the documents are only an example and the integrity verification targets do not have to be documents), a technology using digital signatures is developed. Digital signature technology guarantees the integrity of each electronic document (i.e., preservation of content) by attaching a digital signature to an electronic document and authenticating the generator of the electronic document.
Accordingly, digital signature technology is very useful to prevent unauthorized users from making unauthorized alterations. However, the digital signature technology causes difficulty in the efficient utilization of the electronic documents because an alternation of content of an electronic document made by a modifier, i.e., a user authorized to alter the content of the electronic document, invalidates the digital signature attached to an electronic document, and the invalid digital signature does not guarantee the integrity of the modified electronic document.
Even if the electronic document includes confidential or unnecessary information, the modifier has difficulty in modifying, such as deleting, such information in the electronic document, which drastically degrades user convenience. When a new electronic document excluding confidential or unnecessary information is generated and newly attached with a digital signature, a signer has to generate the signature every time when generating a new electronic document, which is a burden on the signer. Accordingly, a technology is desired that allows unnecessary information to be deleted from electronic documents and guarantees the integrity of the electronic documents without new signatures generated by signers.
For example, a known digital signature technology (a first related art) called a deletable signature technology divides an electronic document into sub-documents and attaches digital signatures to the original electronic document and each sub-document to achieve deletion of a confidential sub-document. The deletable signature technology can guarantee the integrity of a disclosed part of an electronic document and the confidentiality of a confidential part, and thus can increase convenience of the electronic document.
A digital signature technology (a second related art) is also known that divides an electronic document into sub-documents, calculates a hash value for each sub-document, and prompts a signer and a modifier to attach their signatures to a set of the hash values to realize deletion of confidential sub-documents. This digital signature technology can guarantee the integrity of disclosed parts of the electronic document and the confidentiality of confidential parts (i.e., deleted parts), and thus can increase convenience of the electronic document.
Now, a method for deleting a confidential sub-document based on the second related art will be described. FIG. 1 illustrates an overview of signature generation processing based on the second related art. A signer divides an electronic document into a plurality of sub-documents m1 to m4 (or a plurality of originally divided sub-documents m1 to m4 may be used), calculates hash values h1 to h4 for the sub-documents m1 to m4 respectively, and determines a value resulting from concatenation of the hash values h1 to h4. The signer then generates a signature σsigner for the concatenated value of the hash values h1 to h4. The signer sends the electronic document, the concatenated value of the hash values h1 to h4, and the digital signature σsigner to a next user before terminating the processing. Data enclosed in rectangles as disclosed in FIG. 1 is sent.
FIG. 2 illustrates an overview of processing by a first modifier. Upon receiving the electronic document, the concatenated value of the hash values h1 to h4, and the digital signature σsigner from the signer, the first modifier specifies one or more sub-documents to be deleted (e.g., the sub-documents m2 and m4 in FIG. 2) and modifies contents of the sub-documents m2 and m4 to identifiers of the sub-documents m2 and m4 (e.g., character strings “2” and “4” in FIG. 2), respectively. The first modifier then calculates hash values h1, H2 (for the character string of “2”), h3, and H4 (for the character string of “4”) of each sub-document. The first modifier determines a concatenated value of the hash values and generates a digital signature σmodifier1 for the concatenated hash value. Thereafter, the first modifier sends the modified electronic document including the sub-documents m1 and m3 and the character strings “2” and “4”, the concatenated value of the hash values h1, H2, h3, and H4, the digital signature σmodifier1 of the first modifier, the concatenated value of the hash values h1, h2, h3, and h4, and the digital signature σsigner of the signer to a next user before terminating the processing. Data enclosed in rectangles as shown in FIG. 2 is sent.
FIG. 3 illustrates an overview of processing by a second modifier. Upon receiving the modified electronic document, the concatenated hash value and the digital signature of the first modifier, and the concatenated hash value and digital signature of the signer from the first modifier, the second modifier specifies one or more sub-documents to be deleted (e.g., the sub-document m3 in FIG. 3) and modifies content of the sub-document to an identifier of the sub-document (e.g., a character string “3” in FIG. 3). The second modifier then calculates hash values h1, H2, H3, and H4 for the corresponding sub-documents to determine a concatenated value of the hash values and generates a digital signature σmodifier2 for the concatenated hash value. Thereafter, the second modifier sends the modified electronic document including the sub-document m1 and the character strings “2” to “4”, the concatenated value of the hash values h1 and H2-H4 and the digital signature σmodifier2 of the second modifier, the concatenated value of the hash values h1, H2, h3, and H4 and the digital signature σmodifier1 of the first modifier, and the concatenated value of the hash values h1 to h4 and the digital signature σsigner of the signer to a next user before terminating the processing. Data enclosed in rectangles as shown in FIG. 3 is sent.
FIG. 4 illustrates an overview of processing by a verifier. The verifier receives, from the second and last modifier, the modified electronic document including the sub-document m1 and the character strings “238”, “3”, and “4”, the concatenated value of the hash values h1 and H2-H4 and the digital signature σmodifier2 of the second modifier, the concatenated value of the hash values h1, H2, h3, and H4 and the digital signature σmodifier1 of the first modifier, and the concatenated value of the hash values h1 to h4 and the digital signature σsigner of the signer. The verifier then calculates a hash value of each sub-document of the modified electronic document (1). After confirming that the concatenated value of the calculated hash values matches the concatenated hash value of the second modifier, the verifier verifies the second modifier's digital signature for the concatenated hash value (2). The verifier then verifies the first modifier's digital signature for the concatenated hash value of the first modifier to determine the integrity of the concatenated hash value (3). The verifier further verifies the signer's digital signature for the concatenated hash value of the signer to determine the integrity of the concatenated hash value (4). The verifier then compares the concatenated hash value of the signer with those of the modifiers to identify the modifier who has deleted each sub-document. More specifically, a comparison between the concatenated hash value of the signer and that of the first modifier reveals that the first modifier has deleted the sub-documents m2 and m4. Furthermore, a comparison between the concatenated hash value of the first modifier and that of the second modifier reveals that the second modifier has deleted the sub-document m3.
In this way, the digital signature technology according to the second related art permits sub-documents to be deleted, the integrity of remaining sub-documents to be verified, and modifiers having deleted each sub-document to be identified. However, to realize such a function, the signer and the modifier have to calculate and output hash values in proportion to the number of sub-documents. As a result, the verifier processes the number of hash values in proportion to the number of sub-documents and the number of modifiers (more specifically, a×(n+1) hash values when the number of sub-documents and the number of modifiers are represented as “a” and “n”, respectively). Accordingly, the second related art unfortunately decreases data transfer efficiency.
In contrast, in a third related art, the concatenated hash values are not sent. More specifically, as illustrated in FIG. 5, a signer divides an electronic document into a plurality of sub-documents m1 to m4 (or a plurality of sub-documents m1 to m4 originally divided from an electronic document may be used), calculates hash values h1 to h4 of the sub-documents m1 to m4 respectively, and determines a concatenated value of the hash values h1 to h4. The signer then generates a signature σsigner for the concatenated value of the hash values h1 to h4. The signer sends the electronic document including the sub-documents m1 to m4 and the digital signature σsigner to a next user.
Upon receiving the electronic document and the digital signature σsigner from the signer, a first modifier deletes, for example, the sub-documents m2 and m4. The first modifier modifies contents of the sub-documents m2 and m4 to identifiers of the sub-documents m2 and m4 (e.g., character strings “2” and “4” in FIG. 5), respectively. The first modifier then calculates hash values h1, H2 (for the character string “2”), h3, and H4 (for the character string “4”) for the sub-documents. The first modifier determines a concatenated value of the hash values and generates a digital signature σmodifier1 for the concatenated hash value. Thereafter, the first modifier generates for each deleted sub-document, auxiliary data including an ID of the modifier, an ID of the deleted sub-document, and the hash value of the deleted sub-document. The first modifier sends the modified electronic document, the digital signature σsigner of the singer, the auxiliary data (e.g. (modifier1, 2, h2) and (modifier1, 4, h4) in the example of FIG. 5), and the digital signature σmodifier1 of the first modifier to a next user.
Upon receiving, from the first modifier, the modified electronic document, the digital signature σsinger of the signer, the auxiliary data, and the digital signature σmodifier1 of the first modifier, a second modifier deletes, for example, the sub-document m3. The second modifier then modifies content of the sub-document m3 to an identifier of the sub-document m3 (e.g., a character string “3” in FIG. 5). Thereafter, the second modifier calculates hash values h1, H2, H3, and H4 (for the character strings “238”, “3”, and “4”) for the sub-documents respectively, determines a concatenated value of the hash values, and generates a digital signature σmodifier2 for the concatenated hash value. Thereafter, the second modifier generates, for each deleted sub-document, auxiliary data including an ID of the modifier, an ID of the deleted sub-document, and the hash value of the deleted sub-document. The second modifier sends the modified electronic document, the digital signature σsigner of the signer, the auxiliary data (e.g., (modifier1, 2, h2), (modifier1, 4, h4) and (modifier2, 3, h3) in the example of FIG. 5), the digital signature σmodifier1 of the first modifier, and the digital signature σmodifier2 of the second modifier to a next user.
A verifier receives, from the second and last modifier, the modified electronic document, the digital signature σsigner of the signer, the auxiliary data (for example (modifier1, 2, h2), (modifier1, 4, h4), and (modifier2, 3, h3) in FIG. 5), the digital signature σmodifier1 of the first modifier, and the digital signature σmodifier2 of the second modifier. The verifier calculates a hash value for each sub-document of the modified electronic document (11) and verifies the second modifier's digital signature σmodifier2 for a concatenated value of the calculated hash values (12). The verifier further determines the sub-document deleted by the second modifier based on the auxiliary data (e.g., (modifier2, 3, h3)) of the second modifier.
The verifier replaces the hash value H3 calculated in (11)) with the hash value h3 included in the auxiliary data of the second modifier (13). The verifier then verifies the first modifier's digital signature σmodifier1 for a concatenated value of the hash values h1, H2, h3, and H4 (14). Furthermore, the verifier determines the sub-documents deleted by the first modifier based on the auxiliary data (e.g., (modifier1, 2, h2) and (modifier1, 4, h4)) of the first modifier.
The verifier then replaces the hash values H2 and H4 resulting from the replacement in (13) with the hash values h2 and h4 included in the auxiliary data of the first modifier (15). The verifier verifies the signer's digital signature σsigner for a concatenated value of the hash values h1, h2, h3, and h4 (16).
In this way, the number of hash values used by the verifier is reduced. Even so, the third related art handles as many hash values as the deleted sub-documents. Accordingly, when many sub-documents are deleted from an electronic document, auxiliary data volume increases, which unfortunately decreases data transfer efficiency.